package cn.itcast.com.homework.day824;

import java.util.LinkedList;

/**
 * Created by 郭浩 on 2020/8/24 18:42
 */
/*
public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
 }
 */
public class test {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        TreeNode A1 = new TreeNode(3);
        TreeNode A2 = new TreeNode(15);
        TreeNode B1 = new TreeNode(1);
        TreeNode B2 = new TreeNode(5);
        TreeNode B3 = new TreeNode(9);
        TreeNode B4 = new TreeNode(20);
        root.left = A1;
        root.right = A2;
        A1.left = B1;
        A1.right = B2;
        A2.left = B3;
        A2.right = B4;
        boolean validBST = isValidBST(root);
        System.out.println(validBST);
    }
    public static boolean isValidBST(TreeNode root) {
        //假如满足条件，继续向下判断，使用 队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        //使用标记位，只要有一个不满足，跳出循环，改成false
        boolean flag = true;
        //根节点进队列
        queue.offer(root);
        while (!queue.isEmpty()){
            //假如存在子树并且不满足条件跳出
            TreeNode poll = queue.poll();
            if (poll.right != null && poll.right.val < poll.val){
                flag = false;
                break;
            }
            if (poll.left != null && poll.left.val > poll.val){
                flag = false;
                break;
            }
            //将左右子树进队列
            if (poll.left != null){
                queue.offer(poll.left);
            }
            if (poll.right != null){
                queue.offer((poll.right));
            }
        }
        return flag;
    }
}
